#include <stdio.h>

/* 供参考，用于用英文的空格分隔，依次把数组内的元素的值打印到标注输出，并在行末附加一个换行符*/
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
/*
    完成排序后的数组均通过unsorted_array返回；
    三个函数声明中，num_elements为待排序的元素个数。
    可根据需要自行添加其他函数。
*/

/*待排序的数组元素的编号从0开始到num_elements-1。
要求：
1.	实现如下声明的insertion_sort函数。
2.	在把从1到num_elements-1位置上的每个元素放置到合适位置上之后，将此时unsorted_array里的全部元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。比如输入的unsorted_array数组里依次包含4个元素4, 3, 2, 1。那么输出的内容应该如下：
3 4     2 1
2 3 4 1
1 2 3 4

*/
void insertion_sort(int unsorted_array[], int num_elements){
    for (int j = 1; j < num_elements; j++) {
        int key = unsorted_array[j];
        int i = j - 1;
        while (i >= 0 && key < unsorted_array[i]) {
            unsorted_array[i + 1] = unsorted_array[i];
            i--;
        }
        unsorted_array[i + 1] = key;
        print_array(unsorted_array,num_elements);
    }
}


/*待排序的数组元素的编号从0开始到total_num_elements-1。
要求：
1.	实现如下声明的partition函数；永远选择low位置上的元素作为pivot支撑元素；在partition函数返回pivot支撑元素的位置之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。
2.	递归实现如下声明的quick_sort函数；在每次递归时先处理左侧的子数组，再处理右侧的子数组；quick_sort必须调用partition函数获取pivot支撑元素的位置。
3.	比如当输入的unsorted_array数组的元素依次为 3, 1, 2, 5, 4时，输出应该为：
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5

*/
int partition(int L[], int low,  int  high, int total_num_elements){//分割
    int temp = L[low];
    int pivot = L[low];
    while(low < high){
        while(low < high&&L[high] >= pivot){
            --high;
        }
        L[low] = L[high];
        while(low < high && L[low] <= pivot){
            ++low;
        }
        L[high]=L[low];
    }
    L[low] = temp;
    print_array(L,total_num_elements);
    return low;
}
void QSort(int L[], int low,  int  high, int total_num_elements){
    if(low < high){
        int  pivotpos = partition(L,low,high,total_num_elements);

        QSort(L,low,pivotpos-1,total_num_elements);
        QSort(L,pivotpos+1,high,total_num_elements);

    }
}

void quick_sort(int unsorted_array[],int num_elements ){
    int low = 0,high = num_elements-1;
    QSort(unsorted_array,low,high,num_elements);
}


/*
待排序的数组元素的编号从0开始到num_elements-1
要求：
1.	实现如下声明的heap_sort函数。
2.	在每次对已经建好的最大堆进行调整然后把当前根里的最大值放置到合适正确的位置之后、再次调整形成最大堆之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出之后换行。例如：
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/

void max_heap_down(int a[], int start, int end)
{
    int c = start;
    int l = 2 * c + 1;//start的左孩子索引
    int tmp = a[c];
    for (; l <= end; c = l, l = 2 * l + 1)//将c设置为其左孩子，l设置为右孩子
    {
        if (l < end && a[l] < a[l + 1])//如果右孩子小于end，并且,右孩子小于左孩子
            l++;       //将l改为左孩子索引
        if (tmp >= a[l])//如果c的孩子中较大的元素大于父亲节点
            break;   //则跳出循环
        else           //否则
        {
            a[c] = a[l];//将父亲节点和比自己大的孩子结点交换
            a[l] = tmp;
        }
    }
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    int swap;
    for (i = num_elements / 2 - 1; i >= 0; i--)
        max_heap_down(unsorted_array, i, num_elements - 1);
    for (i = num_elements - 1; i > 0; i--)//设置n-1次循环，因为当n-1个节点都按顺序排好以后，最后一个一定是最小值
    {   swap=unsorted_array[i];
        unsorted_array[i]=unsorted_array[0];
        unsorted_array[0]=swap;
        print_array(unsorted_array,num_elements);
        max_heap_down(unsorted_array, 0, i - 1);
    }
}
void main(){
    int test[10]={4,3,2,1};
    insertion_sort( test, 4);
    printf("\n");
    int test1[10]={3,1,2,5,4};
    QSort(test1,0,4,5);
    printf("\n");
    int test2[10]={10,60,12,40,30,8,70};
    heap_sort(test2,7);
}